########################################################################
#  Pyfm - personal finance data-base
#  Copyright (C) 2007,8 Ehud Ben-Reuven
#  udi@benreuven.com
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation version 2.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
########################################################################
"""Infrastructure for creating a "database" of simple objects from "lines".

This module only provides the framework for the database. Other modules implementing the database
should define the different classes of objects in the database by sub-classing "Obj",
the database automatically keeps a record of the order in which the sub-classes where created.
Sub-class define the object tags (names of its data attributes) and if the data stored
in each tag can have multiple values.
Sub-class specify its key structure: an ordered list of tags.
(it is possible to define multiple key structures.)
A key is made by assigning a value to each of the tags in the key structure.
The database can then search for an object which has the same tag-value pairs stored in it.

Objects in the database are created and updated by updating the entire database with lines.
A line contains tag-value pairs. The update is pefromed on each sub-class in the order in 
which they where created. The sub-class key structure is applied to the line content and
a key is created.
A matching object is looked for (or created and added to the database.)
Once found the object tags are updated with the entire line content.
Once completed the followig sub-class is updated.

Limitation:
* A line can not identify two different objects from the same sub-class.

Links between objects:
* When a line updates an object, the object updates back the line with a reference to the object
(the tag is the class name of the object and the value is the object itself.)
Objects in the following sub-classes can have a tag that will keep a reference to the previouse object.
* When an object keeps a reference to another object it also verifies if that object needs to keep a reference to it.
"""

import copy
from flat import stagvalue,parse,print_line,sprint_line,add2line,sobj
from lib import pickle
from objtools import *
import retype

# The root to the database, has an entry for each class of objects. Each entry has in it all the objects of that
# class
class ObjDB(object):
    def __init__(self):
        self.clsdb={}
        self.name2class={}
        self.update_list=[]
        self.lines={}
        self.nline=0
    def add_update(self,key):
        self.update_list+=[key]
    def addclsdb(self,cls,objdict):
        self.name2class[objdict.objcls.__name__]=objdict.objcls
        self.clsdb[cls]=objdict
        self.add_update(cls)
    def getclsdb(self,cls): return self.clsdb[cls]
    def line_clsupdate(self,line):
        for cls in self.update_list:
            self.getclsdb(cls).update(line)
    def line_update(self,line):
        # TODO Check if line contain's 'Line' tag and if so update the existing Line objects.
        # TODO if line contains '_LINE_INDEX_' tag use it instead of adanvcing self.nline
        if not line: return
        # Keep a record of all lines
        # self reference is in the Line tag
        line['Line']=[line]
        # You can't use id(line) as its index because it changes after pickeling
        # You can't use Line itself as an index because its a dicionary and dictonary are not hashable
        line['_LINE_INDEX_']=[self.nline]
        self.lines[self.nline]=line #!ALGO: you dont need this if you define a class 'Line'
        self.nline+=1
        self.line_clsupdate(line)
            
    def get_filter(self,tag,flat_filter):
        """Convert a flat filter to a regular filter"""
        filter={}
        self.build_filter(tag,flat_filter,filter)
        if filter: return filter[tag][0]
        
    def build_filter(self,tag,originalfilter,filter):
        """Build a filter that is appropriate for searching for values of the tag using the tag-value pairs found at originalfilter which is a flat filter.
        This method is used to implement the "tag=:...:" construction in a flat line.
        
        filter is the same as originalfilter if tag is of a simple type.
        However, if tag is a class you only need to search for its keys.
        So you should put in filter only tag-value pairs of tags that appear in one of the key-tag tuples of the class.
        This gets a little bit more complicated because the key-tag used may themself be a class and in that
        case you should first search for objects of those classes using any of the tag-value pairs in originalfilter.
        
        You should start with filter={} and the result will be returned in place in that filter.
        """
        if tag in filter: return # Avoid loops
        
        # Direct conditions on tag in original filter
        # tag is raw but in original filter it may appear with an operation (full)
        for fulltag,rawtag,op in get_filter_tags(originalfilter):
            if tag == rawtag:
                add2line(filter,fulltag,originalfilter[fulltag])
        
        # If tag is a class we need to check if any of its key tags
        # appear in the original filter
        if tag in self.name2class:
            # Add the filter for tag/class only if it has something in it
            newfilter={}
            for keytag in self.name2class[tag].gettags(): self.build_filter(keytag,originalfilter,newfilter)
            #[self.build_filter(keytag,originalfilter,newfilter) for keytuple in self.name2class[tag].ktags for keytag in keytuple]
            if newfilter: add2line(filter,tag,newfilter)
        
                
    def getalllines(self,filter=None):
        """
Return a list of dictonaries of tag-values pairs.
The filter is itself a dictionay.
The keys of the dictionary are made from an operation-code followed by  a tag name.
The possible operation codes are: '!', '!=', '&=', '<', '<=', '>', '>='

In a key having the '!' op-code, the values are taken to be commands that are applied to the tag
part of the key.

All other keys are used to filter out all the lines in the data-base.
Each dictionary in the returned list coresponds to one of the lines
accepted by the filter. Alternativly,
each dictionary item may corespond to a group of filtered lines if a tag with a UNIQUE
command is defined in the filter.
In this case all lines that have the same value for the UNIQUE
tag are grouped togther.

The returned dictionaries contain tags that had the 'PRINT' or 'GET' command in the filter.
The values assigned for these tags are taken from the filter line (or group of lines)
For example: {'!Line':['PRINT']}
will return all lines
[{'Line':[<line0>]},{'Line':[<line1>]...

You can avoid duplicatios by using the 'UNIQUE' or 'GET' commands.
For example: {'!Asset':['GET']}
will return all assets:
[{'Asset':[<asset0>]},{'Asset':[<asset1>]...

The following filter: {'!SECID':['PRINT'],'!Asset':['UNIQUE']}
will return all the SECID values assigned to each Asset:
[{'SECID':['CUSIP=594918104']},
{'SECID':['CUSIP=345370860']},...

If filter is empty, All lines are accepted.
The filter is a tag-values dictionary.
A line is accepted by the filter if every tag in the filter
also appears in the line and there is an overlap in the values of the tag as they appear
in the line and in the filter.

For example, the following filter: {'!Holding':['GET'],'HIDX':[12,200]}
will return the holdings with HIDX equal to 12 and 200.
The following filter {'!SECID':['PRINT'],'Asset':[<asset>]}
will return the values assigned to the SECID tag of the object <asset>

By default the filter value is compared with a line value using the equality ('=')
operator. A filter tag can be prefixed with an operator: '>=','<=','>','<' and in that case
the relation should hold for at least one of the values of the line and one
of the values of the filter that are assigned to the tag.
The line's value should be placed to the left of the operator and the filter's
to the right.

If an operator (including '=') is prefixed with '&' then the relation should hold for
all the filter values (but at least one of the line's values).

If the operator (including the '&' prefix) is prefixed with a '!' then a NOT is performed
on the above test for accepting a line.(don't confuse this with the '!' command operator
which is immediatly followed by the tag name)

If a value in the filter is itself a dictonary then the real value is first computed by
recursivly calling getall to get the unique values that where assigned to the filter's tag
in all lines that matched the filter as it was defined by the value of the tag in the filter.

A filter tag can be prefixed with a '-' in which case it is ignored.
"""
        if not filter: return []
        
        filter_tags=get_filter_tags(filter)

        # List of all lines, this set is not going to change.
        alllines=set(self.lines.keys())
        # At first all lines are acceptable, this list will narrow down to the relevant lines
        lines=alllines

        # Optimization: if we must have a tag which is a class then look only in lines that have that class
        # Build a dictonary of all commands->tags (used also for other things latter)
        command_tags=get_command_tags(filter,filter_tags)
        xlines=[]
        for tag in command_tags.get('GET',[])+command_tags.get('PRINT',[])+command_tags.get('UNIQUE',[]):
            if tag not in self.name2class: continue
            for o in self.getclsdb(self.name2class[tag]).getallobj():
                xlines.extend(o['_LINE_INDEX_'])
        if xlines: lines&=set(xlines)

        # We are going to modify the content of filter with recursive values
        # so make a copy in order to avoid affecting the caller
        filter=filter.copy()
        for tag,raw_tag,op in filter_tags:
            if op in ['!','?','!?']: continue # Not relevant for a command

            #When defining a filter its possible to recursivly define objects.
            #For example: Holding={HIDX=15}
            values=[]
            # FIXME: lvalues is needed for &= operator but is lost outside this loop
            # so for now it can only be used for tags that are classes.
            lvalues=[]
            for v in filter[tag]:
                if isinstance(v,dict) and raw_tag!='Line': # Line instances are also dictonary so you cant know if it is a filter or an instance 
                    # FIXME: see the FIXME notice on lvalues above
                    if op=='&=' and raw_tag not in self.name2class:
                        raise Exception('Not implemented: Recursive value for non class tag '+raw_tag)
                    objs=self.getallobjects(raw_tag,v) # TODO use getall
                    values+=objs
                    lvalues.append(objs)
                else:
                    values.append(v)
                    lvalues.append([v])
            if not values: return []
            filter[tag]=values

            # Optimization: instead of looping on all lines, loop on lines
            # that appeared in at least one Object for each Class tag in filter.
            if raw_tag in self.name2class or raw_tag=='Line':
                #tagidxs = set([lidx for o in values for lidx in o['_LINE_INDEX_']])
                xlines=[]
                for o in values: xlines.extend(o['_LINE_INDEX_'])
                tagidxs=set(xlines)
            elif raw_tag=='_LINE_INDEX_':
                tagidxs = set(values)
            else: continue
                
            if op=='=': lines&=tagidxs
            elif op=='!=': lines-=tagidxs
            elif op=='&=':
                slines=alllines
                for v in lvalues:
                    slines&=tagidxs
                lines&=slines
            else: raise Exception('Illegal operation '+op+' for Class tag '+raw_tag)

        res=[]
        for lidx in lines:
            l = self.lines[lidx]
            ok=True
            for tag,raw_tag,op in filter_tags:
                try:
                    line_values=l[raw_tag]
                except KeyError:
                    if op=='!?': continue
                    # If tag is missing and it needs to be NOT equal to something
                    # then the test is OK...
                    if op=='!=':
                        continue
                    ok=False # regardless of operation, a tag must appear in the line
                    break # AND on all tags
                if raw_tag in self.name2class or raw_tag=='Line' or raw_tag=='_LINE_INDEX_': continue # Already handled class tags
                if op=='!': continue # We will handle post filtering latter
                flt_values=filter[tag]
                do_not=op[0]=='!'
                if do_not: op=op[1:]
                do_and=op[0]=='&'
                if do_and: op=op[1:]
                if op=='=': # Overlap between values
                    if do_and:
                        # Its important that the value from the filter is to the right of the value from the line
                        # otherwise RE class will not work (Actually this comment is not true!?)
                        ok=all(v in line_values for v in flt_values)
                    else:
                        ok=any(v in line_values for v in flt_values)
                elif op=='?': pass
                else:
                    func = {'>=':lambda v1,v2:v1>=v2,
                        '>':lambda v1,v2:v1>v2,
                        '<=':lambda v1,v2:v1<=v2,
                        '<':lambda v1,v2:v1<v2
                        }[op]
                    if do_and:
                        ok=all(any(func(l_v,flt_v) # using func instead of ==
                            for l_v in line_values)
                            for flt_v in flt_values)
                    else:
                        ok=any(any(func(l_v,flt_v) # using func instead of ==
                            for l_v in line_values)
                            for flt_v in flt_values)
                if do_not: ok=not ok
                if not ok: break # AND on all tags
            if ok: res.append(l)
            
        # Perform post filtering commands on the resulting lines
        if not res: return []
        lines=res
                

        # Organize the resulting lines into groups of lines and merge all lines
        # from same group into one line.
        #
        # Start by checking if there is an explicit grouping command: UNIQUE, GET
        uniques=command_tags.get('UNIQUE',[])+command_tags.get('GET',[])
        if len(uniques)>1:
            # FIXME: the unique command has to be re-designed for multiple tags
            raise Exception('Can handle only one UNIQUE/GET in a single line')
        elif len(uniques)==1:
            s=uniques[0]
            res_group={}
            for l in lines:
                line_values=l[s]
                if len(line_values)!=1:
                    raise Exception('Unique tag has multiple values in line')
                l_v=line_values[0]
                try:
                    res_group.setdefault(l_v,[]).append(l)
                except TypeError: # In case l_v is a dict
                    res_group.setdefault(id(l_v),[]).append(l)                                      
            lines=res_group.values()
        elif any(c in command_tags for c in ['SUM', 'IMAX', 'IMIN']):
            # Group togther all lines if we dont have groups and
            # we have a command that implicitly requires grouping.
            lines=[lines]
        else:
            # If there is no need for grouping then every line is a group of its own
            lines=[[l] for l in lines]
            
                
        # Build the results from the group of lines.
        # Every result is made from merging one group.
        # The result contains only the tag requested by the GET, UNIQUE or SUM commands.
        res=[]
        for l in lines: # l is either a group of a single line or a list of lines grouped togther
            res_l={}
            # IMAX and IMIN commands merge lines in a group by taking one of them
            if len(command_tags.get('IMAX',[])+command_tags.get('IMIN',[]))>1:
                raise Exception('Cant handle more than one IMAX/IMIN command')
            for s in command_tags.get('IMAX',[]):
                    l=[max(l,key=lambda r,tag=s: max(r.get(tag,[''])))]
            for s in command_tags.get('IMIN',[]):
                    l=[min(l,key=lambda r,tag=s: min(r.get(tag,[''])))]
            # Build the result by merging all command tags
            for s in set(t for v in command_tags.values() for t in v): # take every tag only once, even if it is used in sveral commands
                # Merge values from all lines into a single line.
                if s in command_tags.get('SUM',[]):
                    # Sum togther all values from all lines, even if they repeat themselves
                    res_l[s]=[sum(v for ll in l for v in ll[s])]
                else:
                    # Build a list of all values
                    # Retain the order of the results so dont use:
                    #   list(set(...)) to find unique values
                    for ll in l:
                        for v in ll[s]:
                            if v not in res_l.setdefault(s,[]):
                                res_l[s].append(v)
            if res_l: res.append(res_l)

        # Finally sort the results. The tags to be sorted should all appear in the results
        # This is true since every command tag appears in the result.
        for s in reversed(command_tags.get('SORT',[])): # we want the first sorting tag to be the most significant so apply it last
                res.sort(key=lambda r,tag=s: min(r.get(tag,['']))) # If a tag has multiple values then take its smallest when comparing with other lines
        if len(command_tags.get('MAX',[])+command_tags.get('MIN',[]))>1:
            raise Exception('Cant handle more than one MAX/MIN command')
        for s in command_tags.get('MAX',[]):
                res=[max(res,key=lambda r,tag=s: max(r.get(tag,[''])))]
        for s in command_tags.get('MIN',[]):
                res=[min(res,key=lambda r,tag=s: min(r.get(tag,[''])))]
        # Remove non-printable items
        for l in res:
            for t in l.keys():
                if t not in command_tags.get('PRINT',[])+command_tags.get('GET',[]):
                    del l[t]
        if len(res)==1 and not res[0]: return []
        return res

    def getall(self,gtag,filter={}):
        """ Get all lines containing gtag and using the filter.
        extract a list of unique values assigned to gtag in these lines.
        """
        # TODO redirect to getallobjects if gtag is a class
        # gtag can also be a Class
        if not isinstance(gtag,str): gtag=gtag.__name__
        # Small optimization for retrieving all objects of a Class
        if not filter and gtag in self.name2class:
            return self.getclsdb(self.name2class[gtag]).getallobj()

        filter=filter.copy() # We dont want to caller to be affected
        filter.setdefault('!'+gtag,[]).append('GET')
        lines=self.getalllines(filter)
        if not lines: return []
        # We take only the first value for gtag from each line because
        # there should be only one value since we specified UNIQUE
        return [l[gtag][0] for l in lines]

    def getobjectfromline(self,cls,line={}):
        """Return an object from key tags found in line
"""                
        if isinstance(cls,str): cls=self.name2class[cls]
        keys=cls.line_getkeys(line)
        if not keys: return
        odict=self.getclsdb(cls)
        for key in keys:
            try:
                return odict[key]
            except KeyError:
                pass

    def getallobjects(self,cls,filter={}):
        """Return a list of all objects of cls that pass the filter.
If filter is not given return all objects.
The filter in this case is the same filter as used for searching for flat lines (getalllines) but it is applied to filtering objects based on their attributes
and not flat lines based on their tag-value pairs.
The tags that appear in the filter can only be attributes of the cls but you can use them with any comparison operation.
If the tag is a class then the values assigned to it can be dictonaries which will be interpreted as filters for objects of the tag's class.
The only filter command used are SORT,MIN,MAX

Note that the content of objects' attributes may be different from that of the lines (due to tools) and as a result you may get different results than searching for lines.

"""
        if isinstance(cls,list):
            objects=cls
            cls=type(objects[0])
        else:
            if isinstance(cls,str): cls=self.name2class[cls]
            clsdb=self.getclsdb(cls)
            objects=None
        if not filter:  return objects if objects else clsdb.getallobj()

        filter_tags=get_filter_tags(filter)     
        
        # Pre-process the values
        filter=filter.copy() # Protect caller from changes
        for tag,raw_tag,op in filter_tags:
            if op in ['!','?','!?']: continue # Not relevant for a command
            # Validate that all filter tags have values
            values=filter[tag]
            if not values: return [] # No values is no match

            # Optimization: Recursivly retrieve dictionary values now and
            # not latter when looping over each object in the DB.
            # this will give a better chance for the keytag lookup to work,
            if objects: continue
            if not isinstance(values[0],dict): continue # FIXME you cant mix dictionary and regular values for same tag
            newvalues=[]
            for v in values:
                newvalues+=self.getallobjects(raw_tag,v) # TODO use getall
            if not newvalues: return []
            filter[tag]=newvalues


        # Optimization - keytag lookup:
        # instead of looping on all objects in the class, check
        # if the filter has tag-value pairs that can be indexed to a set of objects that contain this pair
        # the tags in these pairs where all used as parts of a key to the objects so an object can not escape being indexed.
        if not objects:
            s=None
            new_filter_tags=[]
            for tag,raw_tag,op in filter_tags:
                if (op!='=' or # Not relevant for a command
                    raw_tag not in clsdb.keytags or
                    filter[tag][0].__class__.__name__ not in [raw_tag,'str']): # By default an unclassed tag is a str
                    new_filter_tags.append((tag,raw_tag,op)) # FIXME this should be performed for every value and not just the first
                    continue
                l=set()
                for value in filter[tag]:
                    tagvalue=(raw_tag,value)
                    if tagvalue in clsdb.keytagvalues:
                        l|=clsdb.keytagvalues[tagvalue]
                if s==None:
                    s=l
                else:
                    s&=l
            if s==None:
                # No relevant tag-value pairs found so no optimization.
                objects=clsdb.getallobj()
            else:
                filter_tags=new_filter_tags # We don't need to check tags= that contributed to building the list.
                objects=list(s)

        if all(op=='!' for tag,raw_tag,op in filter_tags):
            res=objects
        else:
            res=[]
            for l in objects:
                ok=True
                for tag,raw_tag,op in filter_tags:
                    line_values=l[raw_tag]
                    # Validate that the object has values
                    if not line_values:
                        if op=='!?': continue #unless we dont want it to have any value
                        # If tag is missing and it needs to be NOT equal to something
                        # then the test is OK...
                        if op=='!=':
                            continue
                        ok=False # regardless of operation, a tag must appear in the line
                        break # AND on all tags
                    if op=='!': continue # We will handle post filtering latter
                    flt_values=filter[tag]
                    do_not=op[0]=='!'
                    if do_not: op=op[1:]
                    do_and=op[0]=='&'
                    if do_and: op=op[1:]
                    if op=='=': # Overlap between values
                        if do_and:
                            # Its important that the value from the filter is to the right of the value from the line
                            # otherwise RE class will not work (Actually this comment is not true!?)
                            ok=all(v in line_values for v in flt_values)
                        else:
                            if not isinstance(flt_values[0],dict):
                                ok=any(v in line_values for v in flt_values)
                            else:
                                # This happens only if the objects argument of this function
                                # was a (hopefully short) list of objects.
                                # As a result the intial optimization
                                # didn't done the conversion from dict to list of objects
                                # TODO you cant mix dictionary and regular values for same tag
                                # TODO You can have dictionary values in filter with a list of objects
                                # only in equality tests and only if the tag is a class.
                                ok=False
                                for v in flt_values:
                                    if self.getallobjects(line_values,v):
                                        ok=True
                                        break
                    elif op=='?': pass
                    else:
                        func = {'>=':lambda v1,v2:v1>=v2,
                            '>':lambda v1,v2:v1>v2,
                            '<=':lambda v1,v2:v1<=v2,
                            '<':lambda v1,v2:v1<v2
                            }[op]
                        if do_and:
                            ok=all(any(func(l_v,flt_v) # using func instead of ==
                                for l_v in line_values)
                                for flt_v in flt_values)
                        else:
                            ok=any(any(func(l_v,flt_v) # using func instead of ==
                                for l_v in line_values)
                                for flt_v in flt_values)
                    if do_not: ok=not ok
                    if not ok: break # AND on all tags
                if ok: res.append(l)
        if not res: return []                              
            
        post_filter(res,filter,filter_tags)
        return res

    def dump(self,fname):
        pickle.dump(self,fname)
    def load(self,fname):
        # Load inplace from a picklefile.
        # Inplace is required so pointers pointing to global db
        # will continue to point to the correct object
        new_db=pickle.load(fname)
        self.clsdb=new_db.clsdb
        self.update_list=new_db.update_list
        self.lines=new_db.lines
        self.nline=new_db.nline
        self.name2class=new_db.name2class
        
# There should be only one instance of ObjDB pointed to by db.
# This is required because Add2objdb need to access it
db=ObjDB()


# ObjDB above is a mapping of Class to ObjDict
# A container of all objects from a specific class
class ObjDict(dict):
    """A dictionary of objects, from a specifice class.
    The key to the dictionary should be tupple of tag-value tuple pairs.
    For example: key=(('tag1',1),) or key=(('tag2','a'),('tag3',3))
    """
    def __init__(self,objcls):
        dict.__init__(self)
        self.objcls=objcls

        # A dictonary of all tag-value pairs used in any of the keys
        # for each keep a set (unique list) of all the objects that contain it
        self.keytagvalues={}
        self.keytags=set([tag for key in objcls.ktags for tag in key])


    def filter_getobj(self,line):
        """Find the first object to have a matching filter to  the line.
        This happens if the filters of the object matches the line.
        Note that this is different from keys_getobj that raise an exception if more than one object is found.
        Note that no object will be created if there is no existing object that matches the line.
        """
        if not self.objcls.filter: return # If the class does not have filters then non of its objects will have filters
        if self.objcls.fixed_filter:
            filter=self.objcls.fixed_filter.copy()
            filter['Line']=[line]
            filter['!Line']=['PRINT']
            if not db.getalllines(filter): return
        if self.objcls.variable_filter:
            variable_filter=self.objcls.variable_filter.copy()
            for tag in variable_filter:
                value=variable_filter[tag]
                if value not in line: return
                variable_filter[tag]=line[value]
            objs=db.getallobjects(self.objcls,variable_filter)
            if objs: return objs[0]
        return
    def keys_getobj(self,keys):
        """Find object using key or  a list of keys.
        If no value is found then new object is created.
        
        If a list of keys is given, it is expected that all keys point to the same object,
        otherwise an error will generate.
        
        Once an object is found or created, all keys are stored to point to the found object.
        """
        if not keys: return None
        if not isinstance(keys,list): keys=[keys]
        objs=[self[key] for key in keys if key in self]
        if len(set(objs))>1:
            print objs
            raise Exception("Conflicting keys")
        # If not found create a new object
        if objs:
            obj=objs[0]
        else:
            obj=self.objcls()
            # Each object has a default key which is the pair (classname,object-itself)
            self[((obj.classname,obj),)]=obj
            # Make sure the object can be represented by at least one of its keys.
            for tag,value in keys[0]:
                obj.update_tag(tag,[value])
        return obj
    def update(self,line):
        """Use information in line to find/create an object,
        update it with line content and update the line with a reference to the object.
        Line returns a list of possible values for every tag or [] if there isn't any.
        Raise an exception if more than one object match the line.    
        """
        keys=self.objcls.line_getkeys(line) # generate keys for the object.
        obj=self.keys_getobj(keys) # find the object or create a new one
        if obj:
            obj.update(line) #  Update the object with all relevant fields in the line.
            # Generate all possible keys on object and make sure they all point to it.
            # Don't just use the keys found in the line because there is a possibility that there
            # are even more new keys generated from combining tags found in the line and tags already exisiting in the object
            for key in obj.getkeys():
                if key in self:
                    if self[key]!=obj:
                        raise Exception('Multiple objects with same key')
                else:
                    self[key]=obj
    
            # The values assigned to tags in the line that are also in use in the key (keytags)
            # can be used as an index for fast access to the object.
            for tag in self.keytags:
                if (tag not in line or
                    line[tag][0].__class__.__name__ not in [tag,'str']): # TODO this should be performed for every value and not just the first
                    continue
                for value in line[tag]:
                    tagvalue=(tag,value)
                    self.keytagvalues.setdefault(tagvalue,set()).add(obj)                                        
        else:
            obj=self.filter_getobj(line)
            if not obj: return
                    
        # Update the line with a reference to the object {object.classname:object}.
        if line.get(obj.classname):
            if len(line[obj.classname])>1 or \
                line[obj.classname][0]!=obj:
                raise Exception("Conflicting objects, a bug?")
        else:
            line[obj.classname]=[obj]
    def unique_values(self):
        """Make sure each object is used once. The same object can appear several times in values
        because an object can have multiple keys"""
        return list(set(self.values()))
    def getallobj(self):
        #""" Return a list of all instances."""
        return self.unique_values()
            
def rstr(l):
    """ Recursive convertion of a tuple/list to a string"""
    if isinstance(l,tuple) or isinstance(l,list) :
        r=[rstr(v) for v in l]
        if len(r)>1:
            if isinstance(l,tuple):
                return '('+','.join(r)+')'
            else:
                return '['+','.join(r)+']'
        else:
            return r[0]
    else:
        return str(l)


class Add2objdb(type):
    """This is a meta class that is designed to create a dictionary for every new class of objects defined.
    It is called by placing the line
    __metaclass__=Add2objdb
    in the definition of the Obj class:
    
According to Python Reference Manual I was supposed to define a function that replaces the built in type(name,base,dict) function
however for some reason when doing this only the creation of Obj class uses this function. All sub-classes derived from Obj don't follow.
    """
    def __init__(cls,name,base,dict):
        global db
        if cls.__name__ != 'Obj': # The Obj class itself, is abstract and should not be used
            # At this point we can add items to the class that are computed from others.
            cls.classinit()
            db.addclsdb(cls,ObjDict(cls))
        super(Add2objdb,cls).__init__(name,base,dict)

#def Add2objdb(name,base,dict):
    #"""This is a meta class that is designed to create a dictionary for every new class of objects defined.
    #It is called by placing the line
    #__metaclass__=Add2objdb
    #in the definition of the Obj class:
    #"""
    #dict['__metaclass__']=staticmethod(Add2objdb)
    #cls=type(name,base,dict)
    #if name != 'Obj': # The Obj class itself, is abstract and should not be used
        #global db
        #db.addclsdb(cls,ObjDict(cls))
    #return cls

class Obj(object):
    """The super-class for all classes of objects in the data base."""
    __metaclass__=Add2objdb # This line creates a dictionary (ObjDict) for the class in objdb
    # In addition, each object has a default pair: <classname>=<self>
    stags=[] # Tag names of single-valued fields
    otags=[] # Tag names of single-valued fields that can be overwritten
    mtags=[] # Tag names of fields that can have multiple values.
    
    ktags=[] # List of different lists of tags that can be used to create a key to the object. [classname] is implicitly assumed.
    etags=[] # define non-key tags that must appear in a flat-line in order for it to contain the object
    filter='' # filter that can apply to a line to test if it contains an object of the class
    
    dtags=[] # Tag names to make a nice string representation of this object
    
    # TODO: when etags is used its possible to have an empty value for ktags (check that this does not cause bugs)
    # objects without a key are useful if their sol usage is to be included in other objects (e.g. model.Money)

    def __init__(self):
        # Allocate lists for every tag
        # all object's tags have a value which is a list
        for f in self.tags: setattr(self,f,[])
        # The name of the object class. The tuple (classname,obj) is used as an additional key.
        setattr(self,self.classname,[self])
    @classmethod
    def classinit(cls):
        """Initialize class items that are computed from the user defined class items.
Don't put here items that are going to be modified after an object will be creared from the class."""
        self=cls
        # Every object keeps a record of all the lines in which it appeared in the _LINE_INDEX_ attribute
        # so add it to mtags.
        # Note: You can't modify attributes that are defined in a class
        # and then store them with pickle (WHY???)
        cls.mtags=copy.copy(cls.mtags)
        if '_LINE_INDEX_' not in cls.stags+cls.otags+cls.mtags: # Check if the subclass has not already defined it
            cls.mtags.append('_LINE_INDEX_')
            
        cls.tags=cls.stags+cls.otags+cls.mtags

        # class name is a special object's tag 
        #self.classname=self.__class__.__name__
        cls.classname=cls.__name__
        # verify that all tags used in a key are also object's tag
        for key in cls.ktags:
            for tag in key:
                if tag not in cls.tags:
                    raise Exception("Key tag %s not an attribute of the class %s"%(tag,cls.classname))
        
        # Each filter in the class is a string that needs to be parsed
        # Note that the default tagtype syntax will be used (you can set it in flat.tagtype_syntax)
        if cls.filter:
            # Split the filter to two parts.
            # One is the same for all objects in the clas and is used to test the line for a match
            # The other is variable. Its values are made from values taken from the object.
            # The variable filter is inversed: instead of a filter applied on the line by each tag it is inverted to be a filter applied on each object by the line.
            filter=parse(cls.filter)
            cls.fixed_filter={}
            cls.variable_filter={}
            for tag in filter.keys():
                value=filter[tag][0] # Empty tags are not expected
                if isinstance(value,str) and value.startswith('@') and value.endswith('@'):
                    t,r,o=break_tag(tag)
                    # =,!=,&= are symetrical operators
                    if o=='>': o='<'
                    elif o=='<': o='<'
                    elif o=='>=': o='<='
                    elif o=='<=': o='>='
                    elif o=='=': o=''
                    cls.variable_filter[o+value[1:-1]]=r
                else:
                    cls.fixed_filter[tag]=filter[tag]
    @classmethod
    def gettags(cls):
        # You cant use self.tags on cls because it is defined latter when subclassing Obj but cls does not contaon .tags which is computed in an Object with __init__
        return list(set(cls.stags+cls.mtags+cls.otags+['_LINE_INDEX_']))

    def update_tag(self,tag,values):
        if tag==self.classname: # self is write protected
            if values and (len(values)>1 or values[0]!=self):
                raise Exception('Attempting to change self')
            return
        if tag in self.mtags:
            for value in values:
                if value not in getattr(self,tag):
                    getattr(self,tag).append(value)
        elif tag in self.stags:
            for value in values:
                if not getattr(self,tag):
                    setattr(self,tag,[value])
                elif value not in getattr(self,tag):
                    print 'Multiple values to single-valued tag in:',stagvalue(self.classname,self)
                    print stagvalue(tag,getattr(self,tag))
                    print stagvalue(tag,value)
                    getattr(self,tag).append(value)
        elif tag in self.otags:
            for value in values:
                setattr(self,tag,[value])
    def update(self,line):
        #self.lines_idx+=line['_LINE_INDEX_'] # ALGO: You dont need this if you define Line or _LINE_INDEX_ to be an mtag of every object
        for s in self.tags:
            values=line.get(s)
            if not values: continue
            self.update_tag(s,values)
            # If this object is going to point at another object then try to update that in pointing to this
            for v in values:
                if isinstance(v,Obj) and v!=self:
                    v.update_tag(self.classname,[self]) # Dont use v.update to avoid cycles
        #self.update_filters()
    #def update_filters(self):
        ## Build a list of filters that will be used to test if a line matches the object. (see ObjDict.filters_getobj)
        ## this test will be performed only if using keys fails.
        ## Each instance of the class needs its own private copy of the filter because of the fact that the filter
        ## can have a test to compare tag values in the line to the object's own tag values.
        #self.parsed_filters=[]
        #for half_parsed_filter in self.half_parsed_filters:
            ## Each filter in the class is a string that needs to be parsed
            ## Note that the default tagtype syntax will be used (you can set it in flat.tagtype_syntax)
            #filter=half_parsed_filter.copy()
            ## In the filter all tags that have a single value that starts with @ are set to point to the object's attribute with the name that follows the @
            #flttags=filter.keys() # we are going to modify parsed_filter so protect the iteration
            #for flttag in flttags:
                #values=filter[flttag]
                #if len(values)==1 and values[0][0]=='@' and values[0][-1]=='@':
                    #objtag=values[0][1:-1]
                    #filter[flttag]=getattr(self,objtag)
            #self.parsed_filters.append(filter)

    #def __eq__(self,other):
        #""" In several places we keep the same object as a value to several keys in the same dictionary.
        #The comparison is used to verify that the two keys are pointing to the same object"""
        #return id(self)==id(other)
    #def __ne__(self,other): return not self.__eq__(other)
    #def __hash__(self):
        #""" Needed in order to build a set of objects"""
        #return id(self)
    def __getitem__(self,key,defval=[]):
        """tags can be accessed in dictionary syntax.
        used in getkeys"""
        if key==self.classname: return [self]
        if key not in self.tags: return []
        return getattr(self,key)
    def get(self,key,defval=[]): # The defval is needed so it will have the same interface as dict
        return self.__getitem__(key) # used by line_getkeys when called by getkeys
    def rget(self,key):
        """Get all values assigned to key, key can be a tag of the object or a tag of any of the objects that are values in this object.
In some way this is the opposite of ObjDB.build_filter"""
        values=self.get(key)
        for tag in self.tags:
            if tag in db.name2class:
                for o in self[tag]:
                    values+=o.rget(key)
        return list(set(values)) # remove duplicates
    def getkeys(self):
        """Return a list of all the currently known keys of this object.
        Each key is an N-tuple made from 2-tuples. Each 2-tuple is made from the tag name and a value assigned
        to it. The list of tags must match one of the definitions a key in ktags (order is important)
        """
        return self.line_getkeys(self)
    def tag_repr(self,tag,all_values=True,skip_objects=False):
        """Return a flat line representing the values of tag."""
        values=self[tag]
        if not values: raise Exception('tag %s has no value'%tag)
        sres=[]
        for value in values:
            sres.append(stagvalue(tag,value))
            #s=None
            #if isinstance(value,Obj):
                #if not skip_objects: s=value.key_repr()
            #elif isinstance(value,basestring):
                #s=stagvalue(tag,value) # This case is needed to avoid extra '' that repr adds to strings
            #else:
                #s=stagvalue(tag,`value`)
            #if s: sres.append(s)
            if sres and not all_values: break
        return ' '.join(sres)
    def key_repr(self):
        """Return a flat line repr of the first non empty key-tuple"""
        for keytuple in self.ktags:
            if all(self[tag] for tag in keytuple):
                return ' '.join(self.tag_repr(tag,all_values=False) for tag in keytuple)
        return ''
    
    def build_line(self,line):
        """Build a minimal flat line made only from simple tags that contains all the information needed to access the object.
        This is used to build a "tag=|...|" description of the object.
        
        You should start with line={} and the result will be in it"""
        # Find the first non empty key tuple
        for keytuple in self.ktags:
            if all(self[tag] for tag in keytuple): break
        assert(keytuple)
        for tag in keytuple:
            if tag in line: continue
            value=self[tag][0]
            if tag in db.name2class:
                value.build_line(line)
            else:
                line[tag]=[value]

    def dict(self):
        """Return a dictionary of all the tags of this object.
        This could be modified by the caller and used as a line when querying the DB"""
        return dict([[tag,self[tag]] for tag in self.tags if self[tag]])
    def __iter__(self): # FIXME: you cant do iteration within an another iter of the same object
        self.index=-1
        return self
    def next(self):
        self.index+=1
        if self.index == len(self.tags):
            raise StopIteration
        return self.tags[self.index]
    def __repr__(self):
        """A flat line that contains all the object information"""
        return '{'+self.key_repr()+'}'
    def print_tags(self):
        """A list of all tags. Start with the key tags,
        followed by tags defined in dtags followed by all the rest. Skip tags begining with _
        """
        s=[tag for keytuple in self.ktags for tag in keytuple]
        s=list(set(s))
        s+=[tag
            for tag in self.dtags
            if tag not in s and tag[0]!='_']
        s+=[tag
            for tag in self.tags
            if tag not in s and tag[0]!='_']
        return s
    
    def sprint(self):
        return sprint_line(self,tags=self.print_tags())
    def pprint1(self,expand,full):
        tags=self.print_tags()
        print_line(self,expand=expand,tags=tags)
        if full:
            for t in tags:
                if t in db.name2class:
                    for o in self[t]:
                        o.pprint1(expand,full)
    def pprint(self,expand=False,full=False):
        """Print the content of the printable tags of the object.
        If expand then print each different tag in a different line
        If full then recursivly call the pprint of every tag that is a class"""
        if full: expand=True
        self.pprint1(expand,full)
        if not expand: print

    def __str__(self):
        if self.dtags:
            return ' '.join([rstr(self[tag]) for tag in self.dtags if self[tag]])
        return sobj(self)
        #keys=self.getkeys()
        #short_keys=[key for key in keys if key[0][0]!=self.classname]
        #return str(set(short_keys))
    @classmethod
    def line_getkeys(cls,line):
        """Return a list of all keys for this object that can be extracted from the line.
        See getkeys for key structure"""
        # Reject lines without etags
        if cls.etags and isinstance(line,dict): # This method can also be called
                # from getkeys and in that case line is the object itself.
            if all(etag not in line for etag in cls.etags):
                return []
        all_keys=[]
        # There are several combinations of tags and in addition the class name is a key by itelf.
        for tags in cls.ktags+[[cls.__name__]]:
            # check that each tag had at least one value in line, otherwise we cant form a key
            # get return None when a tag does not appear in a line
            if not all(line.get(tag) for tag in tags): continue
            # In a key each tag from tags should be paired with one of the possible values it have
            # in line. We want to collect all combinatorial combination of keys.
            keys=[[]]
            for tag in tags:
                # build a list of all possible pairs for tag
                #pairs = zip([tag]*len(line[tag]),line[tag])
                # A tag-value pair can be part of a key to an object only
                # if the value is a specific real value,
                # and not an abstraction of values used as a search pattern in a query.
                # A value is real if its type is the tag, however, some tags
                # are not explicitly defined in model.tagsyntax and in that case
                # the values of these tags are assumed to be str.
                # Example of search patterns are regular expression (<tag>=/<RE-expression>/)
                # or recursive search pattern ( <tag>={<search-filter>} )
                pairs = [(tag,value)
                        for value in line[tag]
                        if not isinstance(value,(dict,retype.RE))]
                        #if isinstance(value,str) or isinstance(value,int) ortag==value.__class__.__name__]
                new_keys=[]
                for pair in pairs:
                    for key in keys:
                        new_keys.append(key+[pair])
                keys=new_keys
            all_keys+=map(tuple,keys)
        return all_keys

if __name__=='__main__':
    class A(Obj):
        stags=['AS1','AS2','AS3']
        mtags=['AM1','AM2','B']
        ktags=[['AS1'],['AM1','AS2']]
        dtags=['AS1']
    class B(Obj):
        stags=['BS1','BS2']
        mtags=['BM1','A']
        ktags=[['BS1']]
    #db.add_update(A) # this adds a second pass which allows A to point back on B
    
    db.line_update({'AS1':[7234],'BS1':[555]}) # Creae an A,B objects and B points to A
    db.line_update({'AM1':[5678],'AS2':[777]}) # Create another A
    db.line_update({'AS1':[3149],'AM2':['hello']}) # Create another A
    db.line_update({'BS1':['bye'],'AS1':[3149]}) # Create another B and make it link to the prev A
    for phase in range(2):
        print "Phase",phase
        if phase==1:
            db.load('jojo')
        print 'A:\n==='
        for a in db.getclsdb(A).getallobj():
            print `a`
        print 'B:\n==='
        for b in db.getclsdb(B).getallobj():
            print `b`
            print b.BS1
        print 'B if AS1=3149\n========'
        for b in db.getallobjects(B,{'AS1':[3149]}): # Get all Bs from all lines in which AS1=3149
            print `b`
        print 'Lines if there is no AS1'
        for l in db.getalllines({'!Line':['PRINT'],'!?AS1':[]}):
            print l['Line'][0]
        if phase==0:
            db.dump('jojo')

    
